import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * 213 打家劫舍2
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
 * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 */
public class Rob2 {

    @Test
    public void test1() {
        Assertions.assertEquals(3, rob(new int[]{2, 3, 2}));
    }

    @Test
    public void test2() {
        Assertions.assertEquals(4, rob(new int[]{1, 2, 3, 1}));
    }

    @Test
    public void test3() {
        Assertions.assertEquals(3, rob(new int[]{1, 2, 3}));
    }


    @Test
    public void test4() {
        Assertions.assertEquals(0, rob(new int[]{0}));
    }

    @Test
    public void test5() {
        Assertions.assertEquals(1, rob(new int[]{1, 1}));
    }

    @Test
    public void test6() {
        Assertions.assertEquals(3, rob(new int[]{1, 2, 1, 1}));
    }

    @Test
    public void test7() {
        Assertions.assertEquals(103, rob(new int[]{1, 3, 1, 3, 100}));
    }

    @Test
    public void test8() {
        Assertions.assertEquals(0, rob(new int[]{0, 0, 0}));
    }

    @Test
    public void test9() {
        Assertions.assertEquals(3, rob(new int[]{2, 1, 1, 2}));
    }

    @Test
    public void test10() {
        Assertions.assertEquals(4077, rob(new int[]{114, 117, 207, 117, 235, 82, 90, 67, 143, 146, 53, 108, 200, 91, 80, 223, 58, 170, 110, 236, 81, 90, 222, 160, 165, 195, 187, 199, 114, 235, 197, 187, 69, 129, 64, 214, 228, 78, 188, 67, 205, 94, 205, 169, 241, 202, 144, 240
        }));
    }


    /**
     * 解法一：在《打家劫舍1》的基础上为数组增加一个纬度
     * @param nums
     * @return
     */
    public int rob(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }

        /*
         * 在打家劫舍1的基础上增加一纬
         * maxProfit[i][0] 表示不打劫第0家时的利润
         * maxProfit[i][1] 表示打劫第0家时的利润
         * */
        int[][] maxProfit = new int[nums.length][2];
        maxProfit[0][0] = 0;
        maxProfit[0][1] = nums[0];
        maxProfit[1][0] = nums[1];
        maxProfit[1][1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            maxProfit[i][0] = Math.max(
                    maxProfit[i - 2][0] + nums[i],
                    maxProfit[i - 1][0]
            );

            maxProfit[i][1] = Math.max(
                    maxProfit[i - 2][1] + nums[i],
                    maxProfit[i - 1][1]
            );

        }

//        return fromRob1(nums);

//        不打劫第0家时的最终总利润
        int doNotRobFirstHome = maxProfit[maxProfit.length - 1][0];
//        打劫第0家时的总利润，因为打劫了第0家，所以要排除掉第i家时的利润，否则会报警
        int robFirstHome = maxProfit[maxProfit.length - 2][1];

//        取最大值
        return Math.max(doNotRobFirstHome, robFirstHome);
    }

    /**
     * 解法二：
     * 根据《打家劫舍 1》改编
     * 唯一和 198. 打家劫舍 1 的区别就是：被打劫的房间是一个环形
     * 第一间和最后一间是相邻的，不可同时窃取
     * 可以等价转换为：打劫第0家到第i-1家   与 打劫第1家到第i家
     * 然后对比两次打劫，谁的利润高
     * 这样就能把《打家劫舍 2》 的问题转换为求解两次《打家劫舍 1》
     *
     * @param nums
     * @return
     */
    private int fromRob1(int[] nums) {
        int[] copy = new int[nums.length - 1];

//      打劫第0家到第i-1家
        System.arraycopy(nums, 0, copy, 0, nums.length - 1);
        Rob1 rob1Obj = new Rob1();
        int includeZero = rob1Obj.rob(copy);

//        打劫第1家到第i家
        System.arraycopy(nums, 1, copy, 0, nums.length - 1);
        int excludeZero = rob1Obj.rob(copy);

//        对比两种方案，谁的收益最高
        return Math.max(includeZero, excludeZero);
    }
}
